package cn.nawang.ebeim.client.version;

import java.util.Arrays;
import java.util.Stack;

/**
 * Given a 2D binary matrix filled with 0's and 1's,
 * find the largest rectangle containing all ones and return its area.
 *  0 0 0 0
 *  1 1 1 1
 *  1 1 1 0
 *  0 1 0 0
 *  return 6 .
 * Created by GanJc on 2016/2/25.
 */
public class MaximalRectangle {

    public static void main(String[] args) {
        char[][]matrix = {{'1'}};
        char[][]matrix5 = {"11".toCharArray()};
        char[][]matrix2 = {{'1','1'},{'1','0'}};
        char[][]matrix3 = {{'1','1','1'},{'1','1','1'},{'1','0','1'}};
        char[][]matrix4 = {{'0','0','0','0'},{'1','1','1','1'},{'1','1','1','0'},{'0','1','0','0'}};
        maximalRectangle(matrix);
        maximalRectangle(matrix5);
        maximalRectangle(matrix2);
        maximalRectangle(matrix3);
        maximalRectangle(matrix4);
    }

    //需转换为LargestRectangleInHistogram问题,遍历每一行,算出直方图数组
    public static int maximalRectangle(char[][]matrix){
        int length = matrix.length;
        int max = 0 ;
        int a [] = new int[length];
        for (int i = 0; i < length; i++) {
            char[] chars = matrix[i];
            if (chars.length>length){
                int b [] = new int[chars.length];
                System.arraycopy(a,0,b,0,a.length);
                a = b ;
            }
            for (int j = 0; j < chars.length ; j++) {
                if(chars[j] =='1'){
                    a[j]++;
                }else {
                    a[j]=0;
                }
            }
            int m = LargestRectangleInHistogram(a);
            if(m>max){
                max = m ;
            }
            System.out.println(Arrays.toString(a));

        }
        System.out.println("------------" + max);
        return max;

    }

    //o(n)解，利用栈压榨时间复杂度
    public static int LargestRectangleInHistogram(int[] a) {
        //数组末位补零
        int b[] = new int[a.length + 1];
        System.arraycopy(a, 0, b, 0, a.length);
        Stack<Integer> s = new Stack();
        int sum = 0;
        for (int i = 0; i < b.length; i++) {
            if (s.empty() || b[i] > b[s.peek()]) { //和栈顶比较
                s.push(i);
            } else {
                int t = s.pop();//弹出
                //这里还需要考虑stack为空的情况
                int width = i;
                if(!s.isEmpty()){
                    width = i - s.peek() - 1 ;
                }
                int max = b[t] * width;
                if (max > sum) {
                    sum = max;
                }
                i--;
            }
        }
        return sum;
    }
}
